package com.topcoder.tccr211;

import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * You work for a very large company that markets many different products. 
 * In some cases, one product you market competes with another. To help deal 
 * with this situation you have split the intended consumers into two groups, 
 * namely Adults and Teenagers. If your company markets 2 products that 
 * compete with each other, selling one to Adults and the other to Teenagers 
 * will help maximize profits. Given a list of the products that compete with 
 * each other, you are going to determine whether all can be marketed such 
 * that no pair of competing products are both sold to Teenagers or both sold 
 * to Adults. If such an arrangement is not feasible your method will return -1. 
 * Otherwise, it should return the number of possible ways of marketing all 
 * of the products.
 * 
 * The products will be given in a String[] compete whose kth element 
 * describes product k. The kth element will be a single-space delimited 
 * list of integers. These integers will refer to the products that the kth 
 * product competes with. For example:
 * 
 * compete = {"1 4",
 *             "2",
 *             "3",
 *             "0",
 *             ""}
 *             
 * The example above shows product 0 competes with 1 and 4, product 1 competes 
 * with 2, product 2 competes with 3, and product 3 competes with 0. Note, 
 * competition is symmetric so product 1 competing with product 2 means 
 * product 2 competes with product 1 as well.
 * 
 * Ways to market:
 * 1) 0 to Teenagers, 1 to Adults, 2 to Teenagers, 3 to Adults, and 4 to Adults
 * 2) 0 to Adults, 1 to Teenagers, 2 to Adults, 3 to Teenagers, and 4 to Teenagers
 * 
 * Your method would return 2. 
 *
 */
public class Marketing {
	public long howMany(String[] compete) {
		int N = compete.length;
		int groups = N;
		HashMap<HashSet, HashSet> opp = new HashMap<HashSet, HashSet>();
		HashSet<Integer>[] belong = new HashSet[N];
		for (int i=0; i<N; i++) {
			belong[i] = new HashSet<Integer>();
			belong[i].add(i);
		}
		
		for (int i=0; i<N; i++) {
			String[] t = compete[i].split(" ");
			for (String o : t) {
				if (o.length() == 0) continue;
				
				int j = Integer.parseInt(o);
				HashSet<Integer> a = belong[i];
				HashSet<Integer> b = belong[j];
				HashSet<Integer> c = opp.get(a);
				HashSet<Integer> d = opp.get(b);
				
				if (a.contains(j)) return -1;
				if (b == c) continue;
				
				if (c != null) b.addAll(c);
				for (int k : b) belong[k] = b;
				if (d != null) a.addAll(d);
				for (int k : a) belong[k] = a;
				groups--;
				opp.put(a, b);
				opp.put(b, a);
			}
		}
		
		long count = 1;
		for (int i=0; i<groups; i++) count *= 2;
		return count;
	}
	
	public long howMany2(String[] compete) {
		int N = compete.length;
		HashSet<Integer>[] adj = new HashSet[N];
		for (int i = 0; i < N; i++) adj[i] = new HashSet<Integer>();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(compete[i], " ");
			while (st.hasMoreTokens()) {
				int j = Integer.parseInt(st.nextToken());
				adj[i].add(j);
				adj[j].add(i);
			}
		}
		
		int groups = 0;
		int[] color = new int[N];
		for (int i=0; i<N; i++) {
			if (color[i] > 0) continue;
			groups++;
			if (!dfs(adj, i, color, 1)) return -1;
		}
		
		long count = 1;
		for (int i=0; i<groups; i++) count *= 2;
		return count;
	}
	
	private boolean dfs(HashSet<Integer>[] adj, int i, int[] color, int c) {
		if (color[i] != 0) {
			return color[i] == c;
		}
		
		color[i] = c;
		for (int t : adj[i]) {
			if (!dfs(adj, t, color, 3-c)) return false;
		}
		return true;
	}
}
